#pragma once
#include "VanEmdeBoasTree.h"

template <size_t K>
bool VanEmdeBoasTreeBase<K>::insertEmpty(size_t x)
{
	_pMin = x;
	_pMax = x;
	return true;
}

template <size_t K>
bool VanEmdeBoasTree<K>::member(size_t x) const
{
	if (x >= Base::u)
		return false;

	if (!Base::_pMin || !Base::_pMax)
		return false;

	if (x == *Base::_pMin || x == *Base::_pMax)
		return true;

	const Cld* pCld = _cluster[high(x)];
	if (!pCld)
		return false;

	return pCld->member(low(x));
}

template <size_t K>
auto VanEmdeBoasTree<K>::successor(size_t x) const->std::optional<size_t>
{
	if (Base::_pMin && x < *Base::_pMin)
		return Base::_pMin;

	size_t highX = high(x);
	size_t lowX = low(x);
	const Cld* pCld = _cluster[highX];
	if (pCld && pCld->max() && lowX < *pCld->max())
	{
		auto offset = pCld->successor(lowX);
		if (offset)
			return index(highX, *offset);
		else
			return std::nullopt;
	}

	if (!_summary)
		return std::nullopt;

	auto nextCluster = _summary->successor(highX);
	if (!nextCluster)
		return std::nullopt;

	const Cld* pNextCld = _cluster[*nextCluster];
	if (!pNextCld)
		return std::nullopt;

	auto offset = pNextCld->min();
	if (!offset)
		return std::nullopt;

	return index(*nextCluster, *offset);
}

template <size_t K>
auto VanEmdeBoasTree<K>::predecessor(size_t x) const->std::optional<size_t>
{
	if (Base::_pMax && x > *Base::_pMax)
		return Base::_pMax;

	size_t highX = high(x);
	size_t lowX = low(x);
	const Cld* pCld = _cluster[highX];
	if (pCld && pCld->min() && lowX > *pCld->min())
	{
		auto offset = pCld->predecessor(lowX);
		if (offset)
			return index(highX, *offset);
		else
			return std::nullopt;
	}

	if (!_summary)
		return std::nullopt;

	auto nextCluster = _summary->predecessor(highX);
	if (!nextCluster)
	{
		if (Base::_pMin && x > *Base::_pMin)
			return Base::_pMin;

		return std::nullopt;
	}

	const Cld* pNextCld = _cluster[*nextCluster];
	if (!pNextCld)
		return std::nullopt;

	auto offset = pNextCld->max();
	if (!offset)
		return std::nullopt;

	return index(*nextCluster, *offset);
}

template <size_t K>
bool VanEmdeBoasTree<K>::insert(size_t x)
{
	if (!Base::_pMin)
		return Base::insertEmpty(x);

	if (x < *Base::_pMin)
		return false;

	size_t highX = high(x);
	size_t lowX = low(x);
	Cld*& pCld = _cluster[highX];
	if (pCld)
		pCld->insert(lowX);
	else
	{
		pCld = new Cld;
		if (!pCld)
			return false;

		if (!_summary)
		{
			_summary = new Cld;
			if (!_summary)
			{
				delete pCld;
				pCld = NULL;
				return false;
			}
		}

		_summary->insert(highX);
		pCld->insert(lowX);
	}

	if (*Base::_pMax < x)
		*Base::_pMax = x;
	
	return true;
}

template <size_t K>
void VanEmdeBoasTree<K>::erase(size_t x)
{
	if (!Base::_pMin || !Base::_pMax)
		return;

	if (*Base::_pMin == *Base::_pMax)
	{
		Base::_pMin.reset();
		Base::_pMax.reset();
		return;
	}

	if (x == *Base::_pMin)
	{
		if (!_summary)
			return;

		auto minCluster = _summary->min();
		if (!minCluster)
			return;

		Cld* pMinCld = _cluster[*minCluster];
		if (!pMinCld)
			return;

		if (!pMinCld->min())
			return;

		Base::_pMin = index(*minCluster, *pMinCld->min());
	}

	size_t highX = high(x);
	size_t lowX = low(x);
	Cld* pCld = _cluster[highX];
	if (!pCld)
		return;

	pCld->erase(lowX);
	if (pCld->min())
	{
		if (x == *Base::_pMax)
			Base::_pMax = index(highX, *pCld->min());

		return;
	}

	_summary->erase(highX);
	if (x != *Base::_pMax)
		return;

	auto maxCluster = _summary->max();
	if (!maxCluster)
	{
		Base::_pMax = Base::_pMin;
		return;
	}

	Cld* pMaxCld = _cluster[*maxCluster];
	if (!pMaxCld)
		return;

	if (pMaxCld->max())
		Base::_pMax = index(*maxCluster, *pMaxCld->max());
}

